package leetcode.array;

import java.util.*;

/**
 * @author wangmaolin1
 * @date 2023/11/9 23:42
 */
public class _nSum {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        return nSum(nums, 4, 0, target);
    }

    public List<List<Integer>> nSum(int[] nums, int nSum, int start, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int sz = nums.length;
        if (nSum < 2 || sz < nSum) {
            return res;
        }
        // 2Sum 是 base case
        if (nSum == 2) {
            // 双指针那一套操作
            int lo = start, hi = sz - 1;
            while (lo < hi) {
                int sum = nums[lo] + nums[hi];
                int left = nums[lo], right = nums[hi];
                if (sum < target) {
                    while (lo < hi && nums[lo] == left) lo++;
                } else if (sum > target) {
                    while (lo < hi && nums[hi] == right) hi--;
                } else {
                    List<Integer>resT=new ArrayList<>();
                    resT.add(left);
                    resT.add(right);
                    res.add(resT);
                    while (lo < hi && nums[lo] == left) lo++;
                    while (lo < hi && nums[hi] == right) hi--;
                }
            }
        } else {

            for (int i = start; i < nums.length; i++) {
                List<List<Integer>> twoRes = nSum(nums, nSum - 1, i + 1, target - nums[i]);
                if (twoRes.size() > 0) {
                    for (List<Integer> tt : twoRes) {
                        tt.add(nums[i]);
                        res.add(tt);
                    }
                }
                while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                    i++;
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Queue<Integer>queue=new PriorityQueue<>((o1, o2) -> o2-o1);
    }
}
